package 经典排序;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-21
 **/

public class No315计算右侧小于当前元素的个数 {

    /**
     * 给你一个整数数组 nums ，按要求返回一个新数组 counts 。
     * 数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
     * <p>
     * 示例 1：
     * 输入：nums = [5,2,6,1]
     * 输出：[2,1,1,0]
     * 解释：
     * 5 的右侧有 2 个更小的元素 (2 和 1)
     * 2 的右侧仅有 1 个更小的元素 (1)
     * 6 的右侧有 1 个更小的元素 (1)
     * 1 的右侧有 0 个更小的元素
     * 示例 2：
     * 输入：nums = [-1]
     * 输出：[0]
     * 示例 3：
     * 输入：nums = [-1,-1]
     * 输出：[0,0]
     *  
     * 提示：
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     */

    public List<Integer> countSmaller(int[] nums) {
        /**
         * 对索引数组进行排序,然后就可以得出答案了
         * 比较时是对nums比较,但是归并改变时是对index数组改变
         */
        this.mergeSort(nums);

        List<Integer> list = new ArrayList<>();

        for (int i : this.count) {
            list.add(i);
        }

        return list;
    }

    public static void main(String[] args) {
        No315计算右侧小于当前元素的个数 n = new No315计算右侧小于当前元素的个数();
        int[] arr = {5, 2, 6, 1};
        List<Integer> result = n.countSmaller(arr);
        System.out.println(JSON.toJSONString(result));
    }

    private int[] count;
    private int[] index;

    private void mergeSort(int[] arr) {

        this.count = new int[arr.length];
        this.index = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            // 索引存索引
            this.index[i] = i;
        }

        int[] tempArr = new int[arr.length];
        this.dfsSplit(arr, tempArr, 0, arr.length - 1);

    }

    // 递归切割,然后排序
    private void dfsSplit(int[] arr, int[] tempArr, int left, int right) {

        if (left >= right) {
            return;
        }

        int mid = (right - left) / 2 + left;
        this.dfsSplit(arr, tempArr, left, mid);
        this.dfsSplit(arr, tempArr, mid + 1, right);
        this.partSort(arr, tempArr, left, right);
    }

    private void partSort(int[] arr, int[] tempArr, int left, int right) {

        if (left == right) {
            return;
        }

        int mid = (right - left) / 2 + left;

        /**
         * index代替了nums去排序,为何要这样呢?因为这样在排序时能知道原始nums中元素对应的下标,方便对每个count作记录。
         * 移动也只是移动index[]数组
         */

        // 本有序,不用排; 不可! 也得排,因为虽然有序了,但是index可能改变了,需要统计
        /**
         * if (arr[this.index[mid]] >= arr[this.index[mid + 1]]) {
         *    return;
         * }
         */

        int sortIndex = left;
        int sortLeft = left;
        int sortRight = mid + 1;

        /**
         * 倒序! 因题目说是计算右侧小于当前元素个数
         */
        // 将temp成为有序数组
        while (sortLeft <= mid && sortRight <= right) {
            if (arr[this.index[sortRight]] >= arr[this.index[sortLeft]]) {
                // 右进
                tempArr[sortIndex++] = this.index[sortRight++];
            } else {
                // 左进,右剩余就是小的
                this.count[this.index[sortLeft]] += (right - sortRight + 1);
                tempArr[sortIndex++] = this.index[sortLeft++];
            }
        }

        // 左边剩余(此时右肯定是没有剩余的,所以count不用+)
        while (sortLeft <= mid) {
            tempArr[sortIndex++] = this.index[sortLeft++];
        }

        // 右边剩余
        while (sortRight <= right) {
            tempArr[sortIndex++] = this.index[sortRight++];
        }

        // 填充原数组
        for (int i = left; i <= right; i++) {
            this.index[i] = tempArr[i];
        }

    }

}
